package com.salim.leetcode.$19;

import java.util.LinkedList;


/**
 * 解法1 使用固定长度队列模拟滑动窗口
 */
public class RemoveNthNodeFromEndofList {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        LimitedQueue<ListNode> qu = new LimitedQueue<>(n+1);
        ListNode first = head;
        ListNode current = head;
        qu.offer(current);
        while (current.next!=null){
            current = current.next;
            qu.offer(current);
        }
        if(n+1<=qu.size()){
            ListNode left = qu.poll();
            ListNode middle = qu.poll();
            ListNode right = qu.poll();
            left.next = right;
            return first;
        }else{
            int minus = n+1-qu.size();
            //相差=1意味着移除第一个元素 即返回第二个元素
            if(minus==1){
                ListNode left = qu.poll();
                ListNode middle = qu.poll();
                return middle;
            }else{
                return null;
            }
        }
    }

    public static void main(String[] args) {
        RemoveNthNodeFromEndofList removeNthNodeFromEndofList = new RemoveNthNodeFromEndofList();
        ListNode one = new ListNode(1);
        ListNode two = new ListNode(2);
        one.next = two;
        ListNode result = removeNthNodeFromEndofList.removeNthFromEnd(one,2);
        System.out.println(result);
        ListNode one1 = new ListNode(1);
        ListNode result1 = removeNthNodeFromEndofList.removeNthFromEnd(one1,1);
        System.out.println(result1);
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        String str =  " ["+this.val+"]";
        if(this.next!=null){
            str += this.next.toString();
        }
        return str;
    }
}


class LimitedQueue<E> extends LinkedList<E> {
    private static final long serialVersionUID = 1L;
    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        super.add(o);
        while (size() > limit) { super.remove(); }
        return true;
    }
}

/**
 * 解法2 与1思路大致相同 不使用队列直接移动node
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        // Advances first pointer so that the gap between first and second is n nodes apart
        for (int i = 1; i <= n + 1; i++) {
            first = first.next;
        }
        // Move first to the end, maintaining the gap
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}
